from collections import defaultdict, deque
from typing import List

class WordLadderSolver:
    @staticmethod
    def find_ladders(beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return []
        
        # 构建邻接表
        adj = defaultdict(set)
        word_length = len(beginWord)
        wordSet.add(beginWord)
        
        # 通用状态字典
        generic_dict = defaultdict(list)
        for word in wordSet:
            for i in range(word_length):
                generic_word = word[:i] + '*' + word[i+1:]
                generic_dict[generic_word].append(word)
        
        # 构建邻接表
        for word in wordSet:
            for i in range(word_length):
                generic_word = word[:i] + '*' + word[i+1:]
                for neighbor in generic_dict[generic_word]:
                    if neighbor != word:
                        adj[word].add(neighbor)
        
        # BFS准备
        distance = {beginWord: 0}
        queue = deque([beginWord])
        found = False
        
        while queue and not found:
            size = len(queue)
            for _ in range(size):
                current_word = queue.popleft()
                current_dist = distance[current_word]
                for neighbor in adj[current_word]:
                    if neighbor == endWord:
                        found = True
                    if neighbor not in distance:
                        distance[neighbor] = current_dist + 1
                        queue.append(neighbor)
        
        if not found:
            return []
        
        # 回溯收集所有最短路径
        result = []
        path = [endWord]
        
        def backtrack(node):
            if node == beginWord:
                result.append(path[::-1])
                return
            for neighbor in adj[node]:
                if distance.get(neighbor, -1) == distance[node] - 1:
                    path.append(neighbor)
                    backtrack(neighbor)
                    path.pop()
        
        backtrack(endWord)
        return result
